package test;

import java.util.ArrayList;
import java.util.List;

//字母大小写全排列：https://leetcode.cn/problems/letter-case-permutation/description/
//时间复杂度：O(n*2^n)

public class LetterCasePermutation {
	public List<String> ret;
    public StringBuilder path;
    public void dfs(String s,int pos){
        if(s.length()==pos){
            ret.add(new String(path.toString()));
            return ;
        }

        char c=s.charAt(pos);
        
        //无论什么字符一定要选
        path.append(c);
        dfs(s,pos+1);
        path.deleteCharAt(path.length()-1);

        //是字母，再选相反的
        if(Character.isLetter(c)){
            c=(Character.isLowerCase(c))?
                                Character.toUpperCase(c):
                                Character.toLowerCase(c);
            path.append(c);
            dfs(s,pos+1);
            path.deleteCharAt(path.length()-1);
        }
    }
    public List<String> letterCasePermutation(String s) {
        ret=new ArrayList<>();
        path=new StringBuilder();
        dfs(s,0);
        return ret;
    }
}
